/**
    算法描述：就是01背包变成了01234背包而已，由原来的2种情况提升至5种情况，做法还是一模一样的
    核心问题：背包问题
    解决所需数据结构+算法：数组 + 01背包算法
**/
#include<iostream>
using namespace std;

int n, m, v[61][3] = {0}, w[61][3] = {0}, dp[10001] = {0};
int ans = -1;

int max(int a, int b) {
    return a>b?a:b;
}

int main () {
    int V, P, Q;
    cin >> m >> n;
    m/=10;
    for (int i=1; i<=n; i++) {
        cin >> V >> P >> Q;
        V/=10;
        if (!Q) {
            w[i][0] = V;
            v[i][0] = V * P;
        } else {
            if (w[Q][1]) {
                w[Q][2] = V;
                v[Q][2] = V * P;
            } else {
                w[Q][1] = V;
                v[Q][1] = V * P;
            }
        }
    }

    // 主体代码
    for (int i=1; i<=n; i++) {
        if (w[i][0]) {
            for (int j=m; j>=w[i][0]; j--) {
                dp[j] = max(dp[j], dp[j-w[i][0]] + v[i][0]);
                if (j>=w[i][0]+w[i][1]) {
                    dp[j] = max(dp[j], dp[j-w[i][0]-w[i][1]] + v[i][0] + v[i][1]);
                }
                if (j>=w[i][0]+w[i][2]) {
                    dp[j] = max(dp[j], dp[j-w[i][0]-w[i][2]] + v[i][0] + v[i][2]);
                }
                if (j>=w[i][0]+w[i][1]+w[i][2]) {
                    dp[j] = max(dp[j], dp[j-w[i][0]-w[i][1]-w[i][2]] + v[i][0] + v[i][1] + v[i][2]);
                }
            }
        }
    }

    cout << dp[m]*10 << endl;
    return 0;
}
